/**
 * 广度优先搜索
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
export var minMutation = function (start, end, bank) {
  if (start === end) return 0
  const keys = ['A', 'C', 'G', 'T'] // 用于每次变化的单个基因
  const bankSet = new Set(bank)
  const visited = new Set() // 记录已经变化过的基因以免重复计算
  if (!bankSet.has(end)) return -1
  const queue = [start]
  visited.add(start)
  let level = 1
  while (queue.length) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const gene = queue.shift()
      // 列出gene可以变化的基因
      for (let j = 0; j < gene.length; j++) {
        for (let k = 0; k < keys.length; k++) {
          if (gene[j] === keys[k]) continue
          const newGene = gene.slice(0, j) + keys[k] + gene.slice(j + 1)
          if (newGene === end) return level
          if (visited.has(newGene) || !bankSet.has(newGene)) continue
          queue.push(newGene)
          visited.add(newGene)
        }
      }
    }
    level++
  }
  return -1
}

/**
 * 官方方法二题解，从bank着手，减少搜索的广度
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
export var minMutation2 = function (start, end, bank) {
  const m = start.length
  const n = bank.length
  // 将每个基因的合法变化关系存储在邻接表 adj 中，每次基因变化搜索只在 adj 中进行即可。
  const adj = new Array(n).fill(0).map(() => new Array())
  let endIndex = -1
  for (let i = 0; i < n; i++) {
    if (end === bank[i]) {
      endIndex = i
    }
    for (let j = i + 1; j < n; j++) {
      let mutations = 0
      for (let k = 0; k < m; k++) {
        if (bank[i][k] !== bank[j][k]) {
          mutations++
        }
        if (mutations > 1) {
          break
        }
      }
      if (mutations === 1) {
        adj[i].push(j)
        adj[j].push(i)
      }
    }
  }
  if (endIndex === -1) {
    return -1
  }

  const queue = []
  const visited = new Array(n).fill(0)
  let step = 1
  // 从start开如搜，找出哪个bank是只变一次的，加入到队列中
  for (let i = 0; i < n; i++) {
    let mutations = 0
    for (let k = 0; k < m; k++) {
      if (start[k] != bank[i][k]) {
        mutations++
      }
      if (mutations > 1) {
        break
      }
    }
    if (mutations == 1) {
      queue.push(i)
      visited[i] = true
    }
  }
  // 队列都是banks中的元素，每次广搜的元素从adj中取出，并加入到队列中
  while (queue.length) {
    const sz = queue.length
    for (let i = 0; i < sz; i++) {
      const curr = queue.shift()
      if (curr === endIndex) {
        return step
      }
      for (const next of adj[curr]) {
        if (visited[next]) {
          continue
        }
        visited[next] = true
        queue.push(next)
      }
    }
    step++
  }
  return -1
}
